/**
 * 
 */
package algorithme;

import java.util.LinkedList;

import programme.Contrainte;
import programme.Expression;
import programme.FonctObjectif;
import programme.ProgDeterministe;
import programme.ProgStochastique;
import programme.Programme;
import programme.Solution;
import programme.SousExpression;
import programme.TypeContrainte;
import programme.TypeVariable;
import programme.Variable;
import programme.VecteurVariables;

/**
 * @author port
 *
 */
public class RelaxationLagrangienne extends Algorithme<Programme> {

	/** Expression de la fonction Lagrangienne */
	protected Expression lagrangien;
	/** Programme de la fonction duale */
	protected Programme fonction_duale;
	/** Programme du Dual Lagrangien */
	protected Programme dual_lagrangien;
	/** omega : variable du Dual Lagrangien */
	protected Variable omega;
	
	/** Listes des solutions trouvées par la fonction duales */
	protected LinkedList<Solution> xi;
	/** Listes des solutions trouvées par le Dual Lagrangien (lamba et omega)*/
	protected LinkedList<Solution> dualSolutions;
	
	
	
	protected VecteurVariables vect;
	/* (non-Javadoc)
	 * @see algorithme.Algorithme#lancer()
	 */
	@Override
	public Solution lancer() throws Exception {
		
		xi = new LinkedList<Solution>();
		dualSolutions = new LinkedList<Solution>();
		
		construireLagrangien();
		construireFonctionDuale();
		construireDualLagrangien();
		
		System.out.println("Lagrangien : " + lagrangien);
		System.out.println("Fonction duale : " + fonction_duale);
		System.out.println("Dual Lagrangien : " + dual_lagrangien);
		
		xi.add(new Solution(prog.getVariables()));
		dualSolutions.add(new Solution(dual_lagrangien.getVariables()));
		
		int i = 0;
		while( i== 0 || conditionArret() ){
			System.out.println("Boucle " + i);
			Solution current = xi.getLast();
			int j = 0;
			Solution lambda = new Solution(dualSolutions.getLast());
			while( current == null || xi.contains(current)){
				current = resoudreFonctionDuale(lambda);
				Double d = lambda.getValeurs().get(dual_lagrangien.getVariables().get(j%dual_lagrangien.getNbVars()));
				lambda.getValeurs().put(dual_lagrangien.getVariables().get(j%dual_lagrangien.getNbVars()), d+1);
			}
			//System.out.println("xi = " + current);
			xi.add(current);
			construireEtAjouterContrainteDualLagrangien(current);
			//System.out.println("Dual = " + dual_lagrangien);
			Solution dual = resoudreDualLagrangien();
			if (dual != null){
				dualSolutions.add(dual);
				System.err.println("Ajout d'une solution dual : " + dual);
			}
			i++;
		}
		
		return xi.getLast();
	}
	
	protected void construireLagrangien(){
		lagrangien = new Expression();
		// On ajoute la fonction objectif au lagrangien
		for (SousExpression sc : prog.getObjectif().getFonction().getSsExpressions()) {
			SousExpression currentSc = new SousExpression();
			currentSc.setCoef(sc.getCoef());
			for (Variable var : sc.getVar()) {
				currentSc.addVariable(var);
			}
			lagrangien.addSousExpression(currentSc);
		}
		
		int i = 0;
		vect = new VecteurVariables("lambda");
		
		// on ajoute les contraintes relachées
		int coefGlobal = ( prog.getObjectif().isMin() ) ? 1 : -1;
		for (Contrainte c : prog.getContraintes()) {
			if( c.isRelax() ){
				int coef = coefGlobal;
				if( c.getType() == TypeContrainte.SUP ){
					coef *= -1;
				}
				Variable l = new Variable(vect, i, TypeVariable.CONTINUE, 0, Double.MAX_VALUE);
				for( SousExpression seC:c.getExpression().getSsExpressions()){
					SousExpression seLag = new SousExpression();
					seLag.setCoef(coef * seC.getCoef());
					seLag.addVariable(l);
					for (Variable var:seC.getVar()){
						seLag.addVariable(var);
					}
					lagrangien.addSousExpression(seLag);
				}
				SousExpression ss = new SousExpression();
				ss.setCoef(-1 * coef * c.getBorne());
				ss.addVariable(l);
				lagrangien.addSousExpression(ss);
				i++;
			}
		}
	}
	
	protected void construireFonctionDuale(){
		fonction_duale = prog.progSansContrainteRelacher();
		fonction_duale.setObjectif(new FonctObjectif(prog.getObjectif().isMin(), lagrangien));
		//fonction_duale.getVecteursVariables().put("lambda", vect);
	}
	
	protected void construireDualLagrangien(){
		VecteurVariables w = new VecteurVariables("w");
		omega = new Variable(w, 1, TypeVariable.CONTINUE, 0, Double.MAX_VALUE);
		Expression e = new Expression();
		e.addVar(omega);
		dual_lagrangien = new ProgDeterministe();
		dual_lagrangien.setObjectif(new FonctObjectif(!prog.getObjectif().isMin(), e));
		dual_lagrangien.getVecteursVariables().put("w", w);
		dual_lagrangien.getVecteursVariables().put("lambda", vect);
	}
	
	protected void construireEtAjouterContrainteDualLagrangien(Solution x){
		double borne = 0;
		//System.out.println("X : " + x);
		Expression expr = new Expression();
		expr.addVar(omega);
		for (SousExpression ss : lagrangien.getSsExpressions()) {
			double coef = ss.getCoef();
			SousExpression sse = new SousExpression(); 
			for (Variable var : ss.getVar()) {
				if( x.getValeurs().containsKey(var) ){
					coef *= x.getValeurs().get(var); 
				}else{
					sse.addVariable(var);
				}
			}
			if( sse.getVar().isEmpty() ){
				borne += coef;
			}else{
				sse.setCoef(-1 * coef);
				expr.addSousExpression(sse);
			}
		}
		
		if( prog.getObjectif().isMin() ){
			dual_lagrangien.addContrainte(new Contrainte(expr, TypeContrainte.INF, borne, false));
		}else{
			dual_lagrangien.addContrainte(new Contrainte(expr, TypeContrainte.SUP, borne, false));
		}
	}
	
	
	protected Solution resoudreFonctionDuale(Solution lamba) throws Exception{
		Programme p = null;
		//System.out.println(lamba);
		if (prog instanceof ProgDeterministe) {
			p = new ProgDeterministe();
		}else if( prog instanceof ProgStochastique){
			p = new ProgStochastique();
		}
		
		p.setVariables(fonction_duale.getVecteursVariables());
		//On remplace lambda dans le programme
		// Fonction objectif
		Expression obj = new Expression();
		for (SousExpression se : fonction_duale.getObjectif().getFonction().getSsExpressions()) {
			double coef = se.getCoef();
			SousExpression sse = new SousExpression(); 
			for (Variable var : se.getVar()) {
				if( lamba.getValeurs().containsKey(var) ){
					coef *= lamba.getValeurs().get(var); 
				}else{
					sse.addVariable(var);
				}
			}
			if( coef != 0){
				sse.setCoef(coef);
				obj.addSousExpression(sse);
			}
		}
		
		p.setObjectif(new FonctObjectif(fonction_duale.getObjectif().isMin(), obj));
		
		// Les contraintes
		for (Contrainte c : fonction_duale.getContraintes()) {
			Expression expr = new Expression();
			double borne = c.getBorne();
			for (SousExpression se : c.getExpression().getSsExpressions()) {
				double coef = se.getCoef();
				SousExpression sse = new SousExpression(); 
				for (Variable var : se.getVar()) {
					if( lamba.getValeurs().containsKey(var) ){
						coef *= lamba.getValeurs().get(var); 
					}else{
						sse.addVariable(var);
					}
				}
				if( sse.getVar().isEmpty() ){
					borne -= coef;
				}else{
					if( coef != 0){
						sse.setCoef(coef);
						expr.addSousExpression(sse);
					}
				}
			}
			p.addContrainte(new Contrainte(expr, c.getType(), borne, c.isRelax()));
		}
		
		p.getVecteursVariables().remove("lamba");
		
		//System.out.println("Fonction duale à résoudre :");
		
		//System.out.println(p);
		
		
		
		// On lance la résolution
		return solver.resoudre(p);
	}
	
	protected Solution resoudreDualLagrangien(){
		try {
			return solver.resoudre(dual_lagrangien);
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
			return null;
		}
	}
	
	protected boolean conditionArret(){
		if( prog.getObjectif().isMin() ){
			return xi.getLast().getResultat() < dualSolutions.getLast().getResultat();
		}else{
			return xi.getLast().getResultat() > dualSolutions.getLast().getResultat();
		}
	}
}
